package com.jack.leetcode.eachProblem06;

public class 二叉树中的最大路径和 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    private static int max = Integer.MIN_VALUE;

    public static int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        dfs(root);
        return max;
    }

    private static int dfs(TreeNode root){
        if (root == null) {
            return 0;
        }
        int result = root.val;
        int left = Math.max(0, dfs(root.left));
        int right = Math.max(0, dfs(root.right));
        int all = result + left + right;
        int two = result + Math.max(left, right);
        max = Math.max(max, Math.max(all, two));
        return two;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(-10);
        root.left = new TreeNode(1);
        System.out.println(maxPathSum(root));
    }
}
